package com.zjb.datastructure;

public class EightQueens {

    public static void main(String[] args) {

        get(0);


    }

    static int[] position = new int[8];

    static void get(int row) {
        //if (row == 8) {
        //    return;
        //}
        //for (int col = 0; col < 8; col++) {
        //    if (isOk(row, col)) {
        //        position[row] = col;
        //        get(row + 1);
        //    }
        //}
        if (row == 8) { // 8 个棋子都放置好了，打印结果
            printQueens();
            return; // 8 行棋子都放好了，已经没法再往下递归了，所以就 return
        }
        for (int column = 0; column < 8; ++column) { // 每一行都有 8 中放法
            if (isOk(row, column)) { // 有些放法不满足要求
                position[row] = column; // 第 row 行的棋子放到了 column 列
                get(row+1); // 考察下一行
            }
        }

    }

    private static void printQueens() {
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < position.length; j++) {
                if (position[i] == j) {
                    System.out.print("Q ");
                } else {
                    System.out.print("* ");
                }
            }
            System.out.println();
        }

        System.out.println();
    }

    private static boolean isOk(int row, int column) {// 判断 row 行 column 列放置是否合适
        int leftup = column - 1, rightup = column + 1;
        for (int i = row-1; i >= 0; --i) { // 逐行往上考察每一行
            if (position[i] == column) return false; // 第 i 行的 column 列有棋子吗？
            if (leftup >= 0) { // 考察左上对角线：第 i 行 leftup 列有棋子吗？
                if (position[i] == leftup) return false;
            }
            if (rightup < 8) { // 考察右上对角线：第 i 行 rightup 列有棋子吗？
                if (position[i] == rightup) return false;
            }
            --leftup; ++rightup;
        }
        return true;
    }


    //private static boolean isOk(int row, int col) {
    //    int leftUp = col - 1, rightUp = col + 1;
    //    for (int i=row-1; i >= 0; i--) {
    //        if (position[i] == col) {
    //            return false;
    //        }
    //        if (leftUp >= 0) {
    //            if (position[i] == leftUp) {
    //                return false;
    //            }
    //        }
    //        if (rightUp <=8) {
    //            if (position[i] == rightUp) {
    //                return false;
    //            }
    //        }
    //
    //        leftUp--;
    //        rightUp++;
    //    }
    //
    //    return true;
    //}


}
